package com.my.code.sort;

import java.util.Arrays;

import static com.my.code.sort.Util.swap;

/**
 * <b>堆排序</b><p>
 * 堆排序 是利用堆这种数据结构的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足：子节点的键值总是小于（或大于）他的父节点<p>
 * 堆又分为大顶堆和小顶堆，一般升序采用大顶堆，降序采用小顶堆
 *
 * @author zzl
 * @date 2020/10/19
 */
public class HeapSort {

    public static void main(String[] args) {
        int[] arr = {4, 6, 8, 5, 9};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void sort(int[] arr) {
        createHeap(arr);//建大顶堆 相当于堆顶是最大值
        for (int i = arr.length - 1; i >= 1; i--) {
            swap(arr, 0, i);//相当于每次将堆顶的元素放到最后
            maxHeap(arr, 0, i);//排除已经放到最后的元素，继续调整堆
        }
    }

    /**
     * 初始建堆，复杂度O(n) 相当于每个元素都要遍历一遍
     */
    private static void createHeap(int[] arr) {
        int mid = arr.length / 2;//按照数组建堆规则，只要取一半即可
        for (int i = mid; i >= 0; i--) {//从中间开始往前建堆
            maxHeap(arr, i, arr.length);//给每一颗小树以及它的子树建堆
        }
    }

    /**
     * 大顶堆
     * arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
     *
     * @param i      数组中的序号，即树顶的序号
     * @param length 数组中要建堆的长度
     */
    private static void maxHeap(int[] arr, int i, int length) {
        int left = i * 2 + 1;
        int right = i * 2 + 2;
        int maxIndex = i;
        if (left < length && arr[left] >= arr[maxIndex]) {
            maxIndex = left;
        }
        if (right < length && arr[right] >= arr[maxIndex]) {
            maxIndex = right;
        }
        if (i != maxIndex) {
            swap(arr, i, maxIndex);//将大值交换到树顶
            maxHeap(arr, maxIndex, length);
        }
    }

    /**
     * 小顶堆
     * arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]
     *
     * @param i      数组中的序号，即树顶的序号
     * @param length 数组中要建堆的长度
     */
    private static void minHeap(int[] arr, int i, int length) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int minIndex = i;
        if (left < length && arr[left] < arr[minIndex]) {
            minIndex = left;
        }
        if (right < length && arr[right] < arr[minIndex]) {
            minIndex = right;
        }
        if (i != minIndex) {
            swap(arr, i, minIndex);//将小值交换到树顶
            minHeap(arr, minIndex, length);
        }
    }


}
